package G.二叉搜索树;

public class _938_二叉搜索树的范围和 {
    /**
     * 自解：采取中序遍历 找到 [low, high]的第一个数开始累加 知道遍历的数值大于high
     * @param root
     * @param low
     * @param high
     * @return
     */

    int ans ;
    public int rangeSumBST(TreeNode root, int low, int high) {

        helper(root,low,high);
        return ans;
    }

    //遍历函数：中序遍历 更新结果数值 只有当前root数值在low到high之间才进行数值操作 否则就往下遍历
    public void helper(TreeNode node,int low, int high){
        if (node == null){
            return;
        }

        helper(node.left,low,high);




        if (node.val>= low && node.val <= high){
            ans += node.val;
        }
        //大于的时候直接退出 不用再遍历了
        if (node.val <= high){
            helper(node.right,low,high);
        }


    }


    /**
     * 题解：深度优先搜索-- 利用左小右大的远离 如果root的数值小 就寻找右边子树即可 如果在两者中间 添加结果 寻找左右两个子树
     *
     */
    int res;
    public int rangeSumBST1(TreeNode root, int low, int high) {

        if (root == null){
            return 0;
        }

        if (root.val < low) {
            rangeSumBST1(root.right, low, high);
        } else if (root.val > high) {
            rangeSumBST1(root.left, low, high);
        } else {
            res += root.val;
            rangeSumBST1(root.left, low, high);
            rangeSumBST1(root.right, low, high);
        }



        return res;
    }
}
